package main

import "fmt"

/* 14. 最长公共前缀 https://leetcode.cn/problems/longest-common-prefix/  */

func ExecQ14() {
	fmt.Println(longestCommonPrefix([]string{"flower", "flow", "flight"}))
	fmt.Println(longestCommonPrefix([]string{"dog", "racecar", "car"}))
}

// 我写的
func longestCommonPrefix1(strs []string) string {
	srs := make([][]rune, 0, len(strs))
	for _, str := range strs {
		srs = append(srs, []rune(str))
	}
	rs := make([]rune, 0, 200)
	loop := 0
	for {
		var c rune = -1
		for _, rss := range srs {
			if len(rss) <= loop {
				return string(rs)
			}
			if n := rss[loop]; c != -1 {
				if c != n {
					return string(rs)
				}
			} else {
				c = n
			}

		}
		if c == -1 {
			break
		}
		loop++
		rs = append(rs, c)
	}
	return string(rs)
}

// 官方的 👍  内存小
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	isCommonPrefix := func(length int) bool {
		str0, count := strs[0][:length], len(strs)
		for i := 1; i < count; i++ {
			if strs[i][:length] != str0 {
				return false
			}
		}
		return true
	}
	minLength := len(strs[0])
	for _, s := range strs {
		if len(s) < minLength {
			minLength = len(s)
		}
	}
	low, high := 0, minLength
	for low < high {
		mid := (high-low+1)/2 + low
		if isCommonPrefix(mid) {
			low = mid
		} else {
			high = mid - 1
		}
	}
	return strs[0][:low]
}
